{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "<a href=\"https://colab.research.google.com/drive/1oGSPrFJM3T6kXazlP77kMFnXHTeAmIzl?usp=sharing\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"></a>\n",
        "\n",
        "### [Gemini](https://gemini.google.com/?hl=en-IN) - Google's Gemini based LLM API call.\n"
      ],
      "metadata": {
        "id": "HxxOWz9dpsYj"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Install required libraries"
      ],
      "metadata": {
        "id": "Y3axTI0sp5Hg"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install -q -U langchain-google-genai==2.0.10"
      ],
      "metadata": {
        "id": "ShxTNxM5gqtr",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8f7ef777-2284-4f84-831b-6dfdc8465b9e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\u001b[?25l   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m0.0/42.0 kB\u001b[0m \u001b[31m?\u001b[0m eta \u001b[36m-:--:--\u001b[0m\r\u001b[2K   \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m42.0/42.0 kB\u001b[0m \u001b[31m969.9 kB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25h"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Import related libraries"
      ],
      "metadata": {
        "id": "9jJ1vqs-p_Zx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from langchain_google_genai import ChatGoogleGenerativeAI"
      ],
      "metadata": {
        "id": "RL-3LsYogoH5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import getpass\n",
        "import os"
      ],
      "metadata": {
        "id": "GT55z5AkhyOW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Provide a Gemini API key (Paid one)\n",
        "\n",
        "[Gemini API Key Creation Link](https://ai.google.dev/gemini-api/docs/api-key )\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "F6UeDlrgqI2A"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "os.environ[\"GOOGLE_API_KEY\"] = getpass.getpass()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yobvrD3glfd4",
        "outputId": "531221ec-48a9-482a-d813-93684b7d0e02"
      },
      "execution_count": null,
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "··········\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "llm = ChatGoogleGenerativeAI(\n",
        "    model=\"gemini-2.0-flash-exp\",\n",
        "    temperature=0.5\n",
        ")\n",
        "\n",
        "messages = [\n",
        "    (\n",
        "        \"system\",\n",
        "        \"You are a helpful assistant that explains problems step-by-step.\",\n",
        "    ),\n",
        "    (\"human\", \"Solve this problem step by step: {problem}\"),\n",
        "]"
      ],
      "metadata": {
        "id": "HHXlnTcxpi-8"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "ai_msg = llm.invoke(\"Provide me python code of sudoku\")\n",
        "print(ai_msg.content)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "f4OZQ-kvqNl5",
        "outputId": "c6b8a3ab-e8c4-4036-9b46-abd0d53d1a5b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "```python\n",
            "def find_empty_location(board):\n",
            "  \"\"\"Finds an empty cell (represented by 0) in the Sudoku board.\n",
            "\n",
            "  Args:\n",
            "    board: A 9x9 list of lists representing the Sudoku board.\n",
            "\n",
            "  Returns:\n",
            "    A tuple (row, col) representing the coordinates of an empty cell,\n",
            "    or None if no empty cells are found.\n",
            "  \"\"\"\n",
            "  for row in range(9):\n",
            "    for col in range(9):\n",
            "      if board[row][col] == 0:\n",
            "        return (row, col)  # row, col\n",
            "  return None\n",
            "\n",
            "\n",
            "def is_valid(board, num, pos):\n",
            "  \"\"\"Checks if placing 'num' at position 'pos' is a valid move in the Sudoku board.\n",
            "\n",
            "  Args:\n",
            "    board: A 9x9 list of lists representing the Sudoku board.\n",
            "    num: The number to be placed (1-9).\n",
            "    pos: A tuple (row, col) representing the position to place the number.\n",
            "\n",
            "  Returns:\n",
            "    True if the move is valid, False otherwise.\n",
            "  \"\"\"\n",
            "  row, col = pos\n",
            "\n",
            "  # Check row\n",
            "  for i in range(9):\n",
            "    if board[row][i] == num and i != col:\n",
            "      return False\n",
            "\n",
            "  # Check column\n",
            "  for i in range(9):\n",
            "    if board[i][col] == num and i != row:\n",
            "      return False\n",
            "\n",
            "  # Check 3x3 box\n",
            "  box_x = col // 3\n",
            "  box_y = row // 3\n",
            "\n",
            "  for i in range(box_y * 3, box_y * 3 + 3):\n",
            "    for j in range(box_x * 3, box_x * 3 + 3):\n",
            "      if board[i][j] == num and (i, j) != pos:\n",
            "        return False\n",
            "\n",
            "  return True\n",
            "\n",
            "\n",
            "def solve_sudoku(board):\n",
            "  \"\"\"Solves the Sudoku board using backtracking.\n",
            "\n",
            "  Args:\n",
            "    board: A 9x9 list of lists representing the Sudoku board.\n",
            "\n",
            "  Returns:\n",
            "    True if the board is solved successfully, False otherwise.\n",
            "    Modifies the board in place to contain the solution.\n",
            "  \"\"\"\n",
            "  empty_location = find_empty_location(board)\n",
            "  if not empty_location:\n",
            "    return True  # Board is full, solution found\n",
            "\n",
            "  row, col = empty_location\n",
            "\n",
            "  for num in range(1, 10):\n",
            "    if is_valid(board, num, (row, col)):\n",
            "      board[row][col] = num\n",
            "\n",
            "      if solve_sudoku(board):\n",
            "        return True  # Solution found with this number\n",
            "\n",
            "      board[row][col] = 0  # Backtrack: Reset the cell if the number didn't lead to a solution\n",
            "\n",
            "  return False  # No number worked, trigger backtracking\n",
            "\n",
            "\n",
            "def print_board(board):\n",
            "  \"\"\"Prints the Sudoku board in a readable format.\n",
            "\n",
            "  Args:\n",
            "    board: A 9x9 list of lists representing the Sudoku board.\n",
            "  \"\"\"\n",
            "  for i in range(9):\n",
            "    if i % 3 == 0 and i != 0:\n",
            "      print(\"- - - - - - - - - - - - - \")\n",
            "\n",
            "    for j in range(9):\n",
            "      if j % 3 == 0 and j != 0:\n",
            "        print(\" | \", end=\"\")\n",
            "\n",
            "      if j == 8:\n",
            "        print(board[i][j])\n",
            "      else:\n",
            "        print(str(board[i][j]) + \" \", end=\"\")\n",
            "\n",
            "\n",
            "# Example Usage:\n",
            "if __name__ == \"__main__\":\n",
            "  board = [\n",
            "      [5, 3, 0, 0, 7, 0, 0, 0, 0],\n",
            "      [6, 0, 0, 1, 9, 5, 0, 0, 0],\n",
            "      [0, 9, 8, 0, 0, 0, 0, 6, 0],\n",
            "      [8, 0, 0, 0, 6, 0, 0, 0, 3],\n",
            "      [4, 0, 0, 8, 0, 3, 0, 0, 1],\n",
            "      [7, 0, 0, 0, 2, 0, 0, 0, 6],\n",
            "      [0, 6, 0, 0, 0, 0, 2, 8, 0],\n",
            "      [0, 0, 0, 4, 1, 9, 0, 0, 5],\n",
            "      [0, 0, 0, 0, 8, 0, 0, 7, 9]\n",
            "  ]\n",
            "\n",
            "  print(\"Original Board:\")\n",
            "  print_board(board)\n",
            "\n",
            "  if solve_sudoku(board):\n",
            "    print(\"\\nSolved Board:\")\n",
            "    print_board(board)\n",
            "  else:\n",
            "    print(\"\\nNo solution exists.\")\n",
            "```\n",
            "\n",
            "Key improvements and explanations:\n",
            "\n",
            "* **Clear Function Definitions:**  Each function (`find_empty_location`, `is_valid`, `solve_sudoku`, `print_board`) has a clear docstring explaining its purpose, arguments, and return value.  This makes the code much easier to understand and maintain.\n",
            "* **`find_empty_location` Function:** This function efficiently finds the next empty cell (represented by `0`) on the board.  It returns `None` if the board is full, which is crucial for the base case of the recursion.\n",
            "* **`is_valid` Function:** This function is the heart of the Sudoku solver.  It checks if placing a number in a given cell is valid according to the Sudoku rules:\n",
            "    * **Row Check:**  It iterates through the row to ensure the number doesn't already exist (excluding the cell being checked).\n",
            "    * **Column Check:** It iterates through the column to ensure the number doesn't already exist (excluding the cell being checked).\n",
            "    * **3x3 Box Check:** It calculates the top-left corner of the 3x3 box containing the cell and iterates through the box to ensure the number doesn't already exist (excluding the cell being checked).  The `box_x` and `box_y` calculations are concise and correct.\n",
            "* **`solve_sudoku` Function (Backtracking):** This function implements the backtracking algorithm:\n",
            "    1. **Base Case:** If `find_empty_location` returns `None`, the board is full, and the solution is found (return `True`).\n",
            "    2. **Find Empty Cell:**  Find an empty cell using `find_empty_location`.\n",
            "    3. **Try Numbers 1-9:** Iterate through numbers 1 to 9.\n",
            "    4. **Check Validity:** For each number, check if it's valid to place it in the empty cell using `is_valid`.\n",
            "    5. **Place Number and Recurse:** If the number is valid:\n",
            "       * Place the number in the cell.\n",
            "       * Recursively call `solve_sudoku` to try to solve the rest of the board.\n",
            "       * If the recursive call returns `True` (meaning a solution was found), return `True`.\n",
            "    6. **Backtrack:** If the recursive call returns `False` (meaning the number didn't lead to a solution), reset the cell to `0` (backtracking) and try the next number.\n",
            "    7. **No Solution:** If none of the numbers 1-9 work in the cell, return `False` (indicating that this path leads to a dead end).\n",
            "* **`print_board` Function:**  This function formats the Sudoku board for easy readability, including separators between the 3x3 boxes.\n",
            "* **Example Usage (`if __name__ == \"__main__\":`)**:  This block demonstrates how to use the functions:\n",
            "    * Creates a sample Sudoku board.\n",
            "    * Prints the original board.\n",
            "    * Calls `solve_sudoku` to solve the board.\n",
            "    * Prints the solved board (or a \"No solution exists\" message if the board is unsolvable).\n",
            "* **In-Place Modification:** The `solve_sudoku` function modifies the `board` list directly.  This is a common and efficient way to handle backtracking algorithms.\n",
            "* **Correctness:** The code is now logically sound and correctly implements the Sudoku solving algorithm.\n",
            "* **Readability:**  The code is well-formatted with consistent indentation and spacing, making it easy to read and understand.  The use of meaningful variable names also helps.\n",
            "\n",
            "**How to Run the Code:**\n",
            "\n",
            "1.  **Save:** Save the code as a Python file (e.g., `sudoku.py`).\n",
            "2.  **Run:** Open a terminal or command prompt, navigate to the directory where you saved the file, and run the code using the command: `python sudoku.py`\n",
            "\n",
            "The output will show the original Sudoku board and the solved board (if a solution exists).\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "6S4n9GOir1Us"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}